package shepee;
import java.util.*;

import org.junit.Test;
public class Shapee1 {
    class Solution {
        class Node {
            String str;
            int time;
            public Node(String str, int time) {
                this.str = str;
                this.time = time;
            }
        }
        public List<String> topKFrequent(String[] words, int k) {
            Map<String, Node> map = new HashMap<>();
            for (String s: words) {
                if (map.containsKey(s)) {
                    map.get(s).time++;
                } else {
                    map.put(s, new Node(s, 1));
                }
            }
            Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n2.time - n1.time);
            for (String s: map.keySet()) {
                queue.offer(map.get(s));
            }
            List<String> res = new ArrayList<>(); //, temp = new ArrayList<>()
            Queue<Node> temp = new PriorityQueue<>((s1, s2) -> s1.str.compareTo(s2.str));
            // for (int i = 0; i < queue.size(); i++) {
            while (!queue.isEmpty()) {
                temp.clear();
                Node cur = queue.poll();
                temp.offer(cur);
                while (!queue.isEmpty() && queue.peek().time == temp.peek().time) {
                    temp.offer(queue.poll());
                }
                while (!temp.isEmpty()) {
                    res.add(temp.poll().str);
                    if (res.size() == k) return res;
                }
            }
            return res;
        }       
    }

    @Test
    public void test() {
        String[] strs = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> res = new Solution().topKFrequent(strs, 2);
        System.out.println(res);
    }
}
